//全排列
class Solution {
    vector<int> path;
    vector<vector<int>> ret;
    bool hash[21];

public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ret;
    }
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!hash[nums[i] + 10]) {
                path.push_back(nums[i]);
                hash[nums[i] + 10] = true;
                dfs(nums);
                hash[nums[i] + 10] = false;
                path.pop_back();
            }
        }
    }
};
//课程表
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> n;
        unordered_map<int, int> in;
        for (auto nums : prerequisites) {
            int a = nums[0];
            int b = nums[1];
            n[b].push_back(a);
            in[a]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (in.count(i) == 0)
                q.push(i);
        }

        while (q.size()) {
            int t = q.front();
            q.pop();
            for (auto& num : n[t]) {
                if (--in[num] == 0)
                    q.push(num);
            }
        }

        for (auto [a, b] : in) {
            if (b != 0)
                return false;
        }
        return true;
    }
};

//解码方法
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        if (s[0] != '0')
            dp[1] += dp[0];
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] != '0')
                dp[i] += dp[i - 1];
            int sum = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (sum >= 10 && sum <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }
};